/*
题目: 数位和相等数对的最大值
给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与  nums[j] 的数位和相等。

请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。

 https://leetcode.cn/contest/weekly-contest-302/problems/max-sum-of-a-pair-with-equal-sum-of-digits/
 */
public class MaximumSum {
    public int maximumSum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<> ();//Key 为 位数和, Value 为 位数和为Key的最大值
        int res = -1; //记录最大前缀和


        for (int x : nums) {
            int digitsSum = getDigitsSum(x); //获取位数和
            if (map.containsKey(digitsSum)) { //如果前面包含了这个位数和
                int prev = map.get(digitsSum); //前面前缀和为此的值
                res = Math.max(prev + x, res);

                if (x > prev) {
                    map.put(digitsSum, x); //覆盖
                }
            } else {
                map.put(digitsSum, x);
            }
        }

        return res;
    }

    private int getDigitsSum(int x) { //获取位数和
        int ret = 0;
        while (x != 0) {
            ret += x % 10;
            x /= 10;
        }
        return ret;
    }
}
